1. Field of the Invention
The present invention relates to a route exploration method which searches for the shortest route between a departure point and a destination.
2. Description of Related Art
An on-vehicle navigator includes a large-capacity memory such as a CD ROM that stores a large amount of map data, a display unit, and a vehicle location detector for detecting a current location of a vehicle. The navigator reads map data indicating a current position of a vehicle from the CD ROM, and draws a map based on the map data on a display screen. A vehicle location mark (location cursor) is fixed at a specific position (for example, in the center) on the display screen and a map is scrolled with the movement of the vehicle: alternatively, the map is fixed on the screen and the vehicle location mark is moved, showing where the current vehicle location is.
Each map stored in the CD ROM is segmented into drawings, for each of which longitudinal and latitudinal width are determined appropriately according to a scale. A road or the like is described as a set of coordinates representing vertices (nodes) indicated by the longitudes and latitudes, and the road is drawn by plotting the nodes sequentially using lines; a road joins two or more nodes. Two nodes are joined to form what is referred to as a link. Map data is, as shown in FIG. 19, divided into four data units (quarter drawings) that correspond to four divisions of one drawing. One data unit corresponds to one screen. Map data is composed of (1) a road layer containing a road list, a node table, an intersection node list, and an adjacent node list, (2) a background layer containing data for graphically displaying roads, buildings, rivers, etc. in map screens, and (3) a character layer containing alphanumeric data for displaying municipal names and road names.
The road layer has the structure shown in FIG. 20. In the road list RDLT, data items such as a road type (expressway, national highway, and other roads), the total number of nodes forming a road, addresses of nodes forming a road in a node table NDTB, and distances to adjacent nodes are listed for each road. The intersection node list CRLT is composed of sets of addresses of nodes in the node table NDTB that lie at the other ends of links extending from intersections (referred to as intersection nodes), where the sets of addresses are provided in one-to-one correspondence with the intersections. The adjacent node list NNLT is concerned with an adjacent node that is one of the nodes which form a road and is defined by data scattered over multiple units, and that is defined by data which lies on a boundary of units and is shared among multiple units (See FIGS. 21a, 21b). The adjacent node list NNLT lists the number of adjacent nodes corresponding to the number of units that share a node, a drawing number, a unit code of a unit containing the portion of the data of the drawing that defines the adjacent node, and an address of the unit in the node table.
In FIG. 21(a), an adjacent node RN defined by data in a unit AU.sub.1 (AU.sub.2) is shared with a unit AU.sub.2 (AU.sub.1). The number of adjacent nodes is therefore one. In FIG. 21(b), an adjacent node RN defined with data in a unit. AU.sub.11 is shared with three units U.sub.12, AU.sub.21, and AU.sub.22. The number of adjacent nodes is therefore 3. The node table NDTB lists all nodes in a map, and includes coordinate information (longitudes and latitudes) of all the nodes, an intersection identification (hereinafter, ID) flag indicating if a particular node is an intersection, a pointer that when the node is an intersection, points to its address in the intersection node list, and that when the node is not an intersection, points to an address of a road, to which the node belongs, in the road list, an adjacent node ID flag indicating whether or not the node is an adjacent node, and a pointer that when the node is an adjacent node, points to its address in the adjacent node list NNLT.
The on-vehicle navigator has a route guidance facility that explores an optimal route which joins a departure point and a destination by the shortest distance, and displays a guidance route on a screen to give the driver travel guidance. The guidance route is displayed by a boldface line in a specific color to be distinguishable from other roads. When actually driving the vehicle, the driver can therefore readily reach his destination.
One known method for providing an optimal route which joins a departure point and a destination is based on a horizontal exploration technique. In this method, road data is referenced to retrieve all intersections in one or multiple adjoining quarter drawings which cover the whole of a square area whose diagonal is a straight line joining a departure point and a destination (including not only authentic intersections but also simple nodes serving as adjacent nodes). (See Appendix for further detail of both the horizontal and Dijkstra exploration.)
According to the known Dijkstra exploration technique, the shortest route can be explored more accurately than the horizontal exploration technique. However, the Dijkstra technique exploration speed is slower than that of the horizontal exploration technique.
In either the horizontal or the Dijkstra technique, even when a route exploration zone is limited to a square area whose diagonal is a straight line joining a departure point and a destination, since all routes included in the area are explored, it takes considerable time to complete the exploration. A driver therefore must wait for a long period of time before receiving route guidance.
As a solution to the above problem, a heuristic exploration technique has been proposed based on experience, where an optimal route resides in a zone defined by a straight line joining a departure point and a destination. Routes deviating from the direction to the destination from the departure point are "trimmed away" or the distances of the routes are weighted, to lower the priorities of such routes. Thus, unnecessary routes are not explored.
However, if a route to be explored is in a suburban or rural area the density of roads is low, only detours (indirect routes) are sometimes available. For example, in FIG. 25, after exploration proceeds to a node CP.sub.x near a destination, unless a route A deviating from the direction to the destination from the departure point is selected, the destination may not be arrived at. However, in such a heuristic exploration, route A is trimmed away, which disables exploration of an optimal route leading to the destination. Due to the lowered priority of route A, disadvantageously it takes excessive time to explore route A.